﻿public class Solution {
    public int LastStoneWeightII(int[] stones)
    {
        int sum = stones.Sum();
        int N = sum / 2;

        int[] dp = new int[N+1];
        for (int i = 0; i < stones.Length; i++)
        {
            for (int j = N; j >= stones[i]; j--)
            {
                dp[j] = Math.Max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return Math.Abs(sum - 2 * dp[N]);
    }

    public static void Main(string[] args)
    {
        int[] stones = [31, 26, 33, 21, 40];
        Solution solution = new Solution();
        int res = solution.LastStoneWeightII(stones);
        Console.WriteLine(res);
    }
}